/**
 * @author 徐楠
 * @date 2022/1/21 16:30
 * @version 1.0
 */

package com.xunan.likou;

public class FibonacciSequence {
    public static void main(String[] args) {
        int result = fib(5);
        System.out.println(result);

    }

    public static int fib(int n) {

        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }

        return fib(n - 1) + fib(n - 2);

    }

    public static int fibPlus1(int n) {
        int a = 0, b = 1, sum;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }

    public static int fibPlus2(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0;
        int q = 0;
        int r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = (p + q) % MOD;
        }
        return r;
    }




}
